{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Coroutines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is a coroutine?\n",
    "\n",
    "The word co actually comes from **cooperative**.\n",
    "\n",
    "A coroutine is a generalization of subroutines (think functions), focused on **cooperation** between routines.\n",
    "\n",
    "If you have some concepts of multi-threading, this is similar in some ways. But whereas in multi-threaded applications the **operating system** usually decides when to suspend one thread and resume another, without asking permission, so-called **preemptive** multitasking, here we have routines that voluntarily yield control to something else - hence the term **cooperative**.\n",
    "\n",
    "We actually have all the tools we need to start looking at this.\n",
    "\n",
    "It is the `yield` statement we studied in the last section on generator functions.\n",
    "\n",
    "Let's dig a little further to truly understand what coroutines are and how they can be used."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll need to first define quickly what a queue is.\n",
    "\n",
    "It is a collection where items are added to the back of the queue, and items are removed from the end of the queue. So, very similar to a queue in a supermarket - you join the queue at the back of the queue, and the person in the front of the queue is the first one to leave the queue and go to the checkout counter.\n",
    "\n",
    "This is also called a First-In First-Out data structure.\n",
    "\n",
    "(For comparison, you also have a **stack** which is like a stack of pancakes - the last cooked pancake is placed on top of the stack of pancakes (called a **push**), and it's the first one you take fomr the stack and eat (called a **pop**) - so that is called First-In Last-Out)\n",
    "\n",
    "We can just use a simple list to act as queue, but lists are not particularly effecient when adding elements to the beginning of the list - they are fine for adding element to the end, but less so at inserting elements, including at the front.\n",
    "\n",
    "So, instead of using a list, let's just use a more efficient data structure for our queue.\n",
    "\n",
    "The `queue` module has some queue implementations, including some very specialized ones. In Python 3.7, it also has the `SimpleQueue` class that is more lightweight.\n",
    "\n",
    "In this case though, I'm going to use the `deque` class (double-ended queue) from the `collections` module - it is very efficient adding and removing elements from both the start and the end of the queue - so, it's very general purpose and widely used. The `queue` implementations are more specialized and have several features useful for multi-tasking that we won't actually need."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can specify a maximum size for the queue when create it - this allows us to limit the number of items in the queue. \n",
    "\n",
    "We can then add and remove items by using the methods:\n",
    "* `append`: appends an element to the right of the queue\n",
    "* `appendleft`: appends an element to the left of the queue\n",
    "* `pop`: remove and return the element at the very right of the queue\n",
    "* `popleft`: remove and return the element at the very left of the queue\n",
    "\n",
    "(Note that I'm avoiding calling it the start and end of the queue, because what you consider the start/end of the queue might depend on how you are using it)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's just try it out to make sure we're comfortable with it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3, 4, 5])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq = deque([1, 2, 3, 4, 5])\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3, 4, 5, 100])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.append(100)\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3, 4, 5, 100])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([-10, 1, 2, 3, 4, 5, 100])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.appendleft(-10)\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([-10, 1, 2, 3, 4, 5])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-10"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.popleft()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3, 4, 5])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can create a capped queue:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "dq = deque([1, 2, 3, 4], maxlen=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3, 4, 100])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.append(100)\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([2, 3, 4, 100, 200])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.append(200)\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([3, 4, 100, 200, 300])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.append(300)\n",
    "dq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see the first item (`2`) was automatically discarded from the left of the queue when we added `300` to the right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also find the number of elements in the queue by using the `len()` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(dq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "as well as query the `maxlen`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.maxlen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are more methods, but these will do for now."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's create an empty queue, and write two functions - one that will add elements to the queue, and one that will consume elements from the queue:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def produce_elements(dq):\n",
    "    for i in range(1, 36):\n",
    "        dq.appendleft(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def consume_elements(dq):\n",
    "    while len(dq) > 0:\n",
    "        item = dq.pop()\n",
    "        print('processing item', item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can use them as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def coordinator():\n",
    "    dq = deque()\n",
    "    producer = produce_elements(dq)\n",
    "    consume_elements(dq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "processing item 1\n",
      "processing item 2\n",
      "processing item 3\n",
      "processing item 4\n",
      "processing item 5\n",
      "processing item 6\n",
      "processing item 7\n",
      "processing item 8\n",
      "processing item 9\n",
      "processing item 10\n",
      "processing item 11\n",
      "processing item 12\n",
      "processing item 13\n",
      "processing item 14\n",
      "processing item 15\n",
      "processing item 16\n",
      "processing item 17\n",
      "processing item 18\n",
      "processing item 19\n",
      "processing item 20\n",
      "processing item 21\n",
      "processing item 22\n",
      "processing item 23\n",
      "processing item 24\n",
      "processing item 25\n",
      "processing item 26\n",
      "processing item 27\n",
      "processing item 28\n",
      "processing item 29\n",
      "processing item 30\n",
      "processing item 31\n",
      "processing item 32\n",
      "processing item 33\n",
      "processing item 34\n",
      "processing item 35\n"
     ]
    }
   ],
   "source": [
    "coordinator()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But suppose now that the `produce_elements` function is reading a ton of data from somewhere (maybe an API call that returns course ratings on some Python course :-) ).\n",
    "\n",
    "The goal is to process these after some time, and not wait until all the items have been added to the queue - maybe the incoming stream is infinite even.\n",
    "\n",
    "In that case, we want to \"pause\" adding elements to the queue, process (consume) those items, then once they've all been processed we want to resume adding elements, and rinse and repeat."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll use a capped `deque`, and change our producer and consumers slightly, so that each one does it's work, the yields control back to the caller once it's done with its work - the producer adding elements to the queue, and the consumer removing and processing elements from the queue:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def produce_elements(dq, n):\n",
    "    for i in range(1, n):\n",
    "        dq.appendleft(i)\n",
    "        if len(dq) == dq.maxlen:\n",
    "            print('queue full - yielding control')\n",
    "            yield\n",
    "        \n",
    "def consume_elements(dq):\n",
    "    while True:\n",
    "        while len(dq) > 0:\n",
    "            print('processing ', dq.pop())\n",
    "        print('queue empty - yielding control')\n",
    "        yield\n",
    "    \n",
    "def coordinator():\n",
    "    dq = deque(maxlen=10)\n",
    "    producer = produce_elements(dq, 36)\n",
    "    consumer = consume_elements(dq)\n",
    "    while True:\n",
    "        try:\n",
    "            print('producing...')\n",
    "            next(producer)\n",
    "        except StopIteration:\n",
    "            # producer finished\n",
    "            break\n",
    "        finally:\n",
    "            print('consuming...')\n",
    "            next(consumer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "producing...\n",
      "queue full - yielding control\n",
      "consuming...\n",
      "processing  1\n",
      "processing  2\n",
      "processing  3\n",
      "processing  4\n",
      "processing  5\n",
      "processing  6\n",
      "processing  7\n",
      "processing  8\n",
      "processing  9\n",
      "processing  10\n",
      "queue empty - yielding control\n",
      "producing...\n",
      "queue full - yielding control\n",
      "consuming...\n",
      "processing  11\n",
      "processing  12\n",
      "processing  13\n",
      "processing  14\n",
      "processing  15\n",
      "processing  16\n",
      "processing  17\n",
      "processing  18\n",
      "processing  19\n",
      "processing  20\n",
      "queue empty - yielding control\n",
      "producing...\n",
      "queue full - yielding control\n",
      "consuming...\n",
      "processing  21\n",
      "processing  22\n",
      "processing  23\n",
      "processing  24\n",
      "processing  25\n",
      "processing  26\n",
      "processing  27\n",
      "processing  28\n",
      "processing  29\n",
      "processing  30\n",
      "queue empty - yielding control\n",
      "producing...\n",
      "consuming...\n",
      "processing  31\n",
      "processing  32\n",
      "processing  33\n",
      "processing  34\n",
      "processing  35\n",
      "queue empty - yielding control\n"
     ]
    }
   ],
   "source": [
    "coordinator()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice a **really important** point here - the producer and consumer generator functions do not use `yield` for iteration purposes - they are simply using `yield` to suspend themselves and cooperatively hand control back to the caller - our coordinator function in this case.\n",
    "\n",
    "The generators used `yield` to cooperatively suspend themselves and yield control back to the caller.\n",
    "\n",
    "Similarly, we are not using `next` for iteration purposes, but more for starting and resuming the generators.\n",
    "\n",
    "This is a fundamentally different idea than using `yield` to implement iterators, and forms the basis for the idea of using generators as coroutines."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Timings using Lists and Deques for Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see some timing differences between `lists` and `deques` when inserting and popping elements. We'll compare this with appending elements to a `list` as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from timeit import timeit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "list_size = 10_000\n",
    "\n",
    "def append_to_list(n=list_size):\n",
    "    lst = []\n",
    "    for i in range(n):\n",
    "        lst.append(i)\n",
    "\n",
    "def insert_front_of_list(n=list_size):\n",
    "    lst = []\n",
    "    for i in range(n):\n",
    "        lst.insert(0, i)\n",
    "        \n",
    "lst = [i for i in range(list_size)]\n",
    "def pop_from_list(lst=lst):\n",
    "    for _ in range(len(lst)):\n",
    "        lst.pop()\n",
    "        \n",
    "lst = [i for i in range(list_size)]\n",
    "def pop_from_front_of_list(lst=lst):\n",
    "    for _ in range(len(lst)):\n",
    "        lst.pop(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's time those out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8679745109602663"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timeit('append_to_list()', globals=globals(), number=1_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20.793169873565148"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timeit('insert_front_of_list()', globals=globals(), number=1_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0017591912596799375"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timeit('pop_from_list()', globals=globals(), number=1_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.012326529086294613"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timeit('pop_from_front_of_list()', globals=globals(), number=1_000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, insert elements at the front of the list is not very efficient compared to the end of the list. So lists are OK to use as stacks, but not as queues.\n",
    "\n",
    "The standard library's `deque` is efficient at adding/removing items from both the start and end of the collection:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "list_size = 10_000\n",
    "\n",
    "def append_to_deque(n=list_size):\n",
    "    dq = deque()\n",
    "    for i in range(n):\n",
    "        dq.append(i)\n",
    "\n",
    "def insert_front_of_deque(n=list_size):\n",
    "    dq = deque()\n",
    "    for i in range(n):\n",
    "        dq.appendleft(i)\n",
    "        \n",
    "dq = deque(i for i in range(list_size))\n",
    "def pop_from_deque(dq=dq):\n",
    "    for _ in range(len(lst)):\n",
    "        dq.pop()\n",
    "        \n",
    "dq = deque(i for i in range(list_size))\n",
    "def pop_from_front_of_deque(dq=dq):\n",
    "    for _ in range(len(lst)):\n",
    "        dq.popleft()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8704001035901001"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timeit('append_to_deque()', globals=globals(), number=1_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8407907529494878"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timeit('insert_front_of_deque()', globals=globals(), number=1_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.000532037516904893"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timeit('pop_from_deque()', globals=globals(), number=1_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0005195763528718089"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timeit('pop_from_front_of_deque()', globals=globals(), number=1_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
